package eashrine;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-11-11-16:18
 * @Description: 1.0
 */
public class T0765 {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pre = new int[n];
        Arrays.fill(pre, -1);
        int cnt = 0;
        for (int i = 0; i < n; i += 2) {
            int x = row[i], y = row[i + 1];
            if (getPre(x, pre) == getHalf(y)) cnt++;
            pre[x] = y;
            pre[y] = x;
        }
        return n / 2 - cnt;
    }

    public int getHalf(int x) {
        return x % 2 == 0 ? x + 1 : x - 1;
    }

    public int getPre(int x, int[] pre) {
        x = getHalf(x);
        while (pre[x] != -1) x = getHalf(pre[x]);
        return getHalf(x);
    }

}
